# 71/100 栈-字符串解码
# leetcode第155题: https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/27
from leetcode.test import test_function as tf
import re


def decodeString_regex(s: str) -> str:
    pattern = r'(\d+)\[([a-zA-Z]*)\]'
    while re.search(pattern, s):
        # 替换匹配的模式
        s = re.sub(pattern, lambda match: int(match.group(1)) * match.group(2), s)
    return s


def decodeString_stack(s: str) -> str:
    """
    举例说明: ab3[a2[c]]ed -> ab acc acc acc ed
    遍历 'ab':    res="ab"            stack=[]
    遍历 '[':     res=""              stack=[('ab', 3)]
    遍历 'a':     res="a"             stack=[('ab', 3)]
    遍历 '[':     res=""              stack=[('ab', 3), ('a', 2)]
    遍历 'c':     res="c"             stack=[('ab', 3), ('a', 2)]
    遍历 ']':     res="acc"           stack=[('ab', 3)]
    遍历 ']':     res="abaccaccacc"   stack=[]
    遍历 'ed':    res="abaccaccacced" stack=[]
    """
    stack = []
    count = 0
    res = ""
    for c in s:
        if c.isdigit():
            count = count * 10 + int(c)
        elif c == "[":
            stack.append((res, count))
            res, count = "", 0
        elif c == "]":
            pre_str, mul = stack.pop()
            res = pre_str + mul * res
        else:
            res += c
    return res


if __name__ == '__main__':
    inp = [{"s": "abc4[a]abcd5[e]d"}, {"s": "abc2[def]"}, {"s": "abc4[a]"}, {"s": "3[a]2[bc]"}, {"s": "ab3[a2[c]]ed"}, ]
    out = ["abcaaaaabcdeeeeed", "abcdefdef", "abcaaaa", "aaabcbc", "abaccaccacced"]
    tf(decodeString_regex, inp, out)
    tf(decodeString_stack, inp, out)
